package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no33;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        //[5,1,2,3,4]
        //1
//        int[] nums = {5, 1, 2, 3, 4};
//        int target = 5;
//        int[] nums = {1, 2, 3, 4, 5};
//        int target = 4;

        int[] nums = {2, 3, 4, 5, 1};
        int target = 6;
        System.out.println(solution.search(nums, target));
    }

    public int search(int[] nums, int target) {
        return search(nums, 0, nums.length - 1, target);
    }

    public int search(int[] nums, int l, int r, int target) {

        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (target < nums[mid]) {
                // 5 1 2 3 4
                if (nums[l] > nums[mid]) {
                    r = mid - 1;
                } else if (nums[mid] > nums[r]) {
                    if (target < nums[l]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                } else {
                    r = mid - 1;
                }
            } else {
                // target > mid
                if (nums[l] > nums[mid]) {
                    // 4 5 1 2 3
                    if (target > nums[r]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                } else if (nums[mid] > nums[r]) {
                    //  2 3 4 5 1
                    l = mid + 1;
                } else {
                    // l < mid && mid < r
                    l = mid + 1;
                }
            }
        }
        return l == r && nums[l] == target ? l : -1;
    }


}
